STL源码剖析_各容器一览

STL中的容器非常好用，是已经实现好的各种数据结构，并且效率也比较高。
掌握各个容器的特性，才能在不同情况下选择合适的容器并正确使用。
本文简单总结了STL的学习步骤，并整理了各容器的特性、适用情况，不涉及具体细节。

STL结构 & 学习步骤

如下图所示，泛型编程、空间配置器、traits特性萃取是STL的基石，以及迭代器，应当先进行学习。
迭代器是连接算法与容器的桥梁，一套算法的实现可以通过不同容器的迭代器来访问容器中的元素，极大简化了代码。
容器分为两大类，分别是序列式容器和关联式容器。

序列式容器中stack和queue的底层是deque，priority_queue的底层是heap。
关联式容器中有两类，一类是借助红黑树，一类是借助hashtable。

各容器总结

vector

简介

简单的说来，vector是一个智能的数组，跟C语言原生数组很像，也是使用的连续线性空间，但也有后者不具备的一些优点。
首先vector中实现了一些常用的方法，比如insert(),push_back()等。另外C语言中的array长度是固定的，vector给提供了自动增长机制。
在执行push_back操作时，如果之前申请的空间用完了，会重新开辟一块二倍于原来的的空间。

备注

使用vector时，如果可以预估其元素数量，可以在创建vector对象时就预先分配足够的内存，可以省去后期多次开辟新空间的开销

list

简介

list是一个双向链表，其节点结构如下：

template <class T>
struct __list_node{
    typedef void* void_pointer;
    void_pointer prev;
    void_pointer next;
    T data;
}

deque

简介

vector是一个单向开口的连续线性空间，可以push_back(),但没有push_front()。deque是一个双向开口的连续线性空间，可以在两端进行插入和删除操作。
由于提供双向操作，随着元素个数增长，会导致预先申请的空间用尽，为了省去重新申请空间，再复制元素的开销，就导致deque的结构是一段段的连续空间，如下图所示：

其中map数组相当于索引，其中每个元素都是指针，指向一段连续空间。
deque的迭代器的结构如下：

备注

如果你要对deque中的元素进行排序，那效率当然会很低，可以将元素拷贝到vector，排序完后再拷贝回去。

stack & queue

简介

这两个容器也叫配接器，底层默认都是deque，分别根据栈和队列的特性有选择的开放deque的接口。

备注

也可以指定list作为底层容器：

stack<int,list<int> > stack1;

不过实际测试并不如deque的快。

priority_queue

简介

priority_queue名为优先队列，该队列始终保持每次出队的元素是最大值或最小值，其内部维护了一个”堆”，可以是大根堆或小跟堆。

slist

简介

单向链表。

set multiset map multimap

简介

set集合，每个元素都是唯一的，multiset允许重复元素存在。
map映射，他的每个元素都是pair(键值对)，但map中键值是唯一的，multimap允许键值重复。
这几个底层全部红黑树实现，红黑树也是一种基本平衡的二叉搜索树，关于学习红黑树，强烈推荐红黑树作者的课件，我的另一篇笔记提供了资料。

备注

使用set时，注意一旦调用[]操作符，然后[]中的键值就添加到集合中了。

map<int,int> map1;
cout<<map1.count(1)<<endl;  //0
cout<<map1[1]<<endl;  //0
cout<<map1.count(1)<<endl;  //1

hashset hash_multiset hashmap hash_multimap

简介

这几个的容器与前面四个不同之处在于，这几个的底层都是hash_table，也就是hash表，其结构如下：

备注

• 其实大部分容器结构都已经在数据结构课程中学过了，所以学习stl的重难点就落在了泛型编程、空间配置器、traits类型萃取，红黑树，deque上面。
• 等读完effective stl可以再来补充本篇笔记。

参考

• 《STL源码剖析》

欢迎与我分享你的看法。
转载请注明出处：http://taowusheng.cn/